Multi-Core Ant Colony Optimization for TSP in Scala

This is a continuation of Parallel Ant Colony Optimization for TSP in Standard ML, Multi-Core Ant Colony Optimization for TSP in Haskell, and Multi-Core Ant Colony Optimization for TSP in Erlang. See first page for Ant Colony and TSP problem description. Here the program has been rewritten in the programming language Scala.

Scala is a hybrid functional and object-oriented programming language. It is based on the Java JVM, so it has available Just-in-Time (JIT) native compilation and native thread support. It has access to the wide variety of class libraries available for Java.

Like Erlang, Scala supports an Actor-style message-passing concurrency model. More traditional thread-based concurrency with locks and shared memory is also available. Unlike Erlang and Haskell, Scala values are not immutable. Like SML and Haskell, typing is static with type inference.


All tests performed on Intel Core2 Quad CPU 2.4 GHz, 2 GB memory.
All on Debian Linux quad 2.6.22-3-686 #1 SMP Sun Feb 10 20:20:49 UTC 2008 i686
except Scala, which was tested on same machine running Windows Vista SP1, because I didn't want to deal with replacing GNU Java with Sun Java. Scala wasn't happy with GNU Java.


All from Debian apt-get, except Scala. Java from Sun.
Erlang 5.6.2
GHC Haskell 6.8.2
MLton SML 20070826
Alice SML 1.4
OCaml 3.10.2
java version "1.6.0_10-beta"
Java(TM) SE Runtime Environment (build 1.6.0_10-beta-b23)
Java HotSpot(TM) Client VM (build 11.0-b11, mixed mode, sharing)

Command Lines

mlton mlton_ant.sml
time ./mlton_ant 1 5 1000 200        (result *4)

alicec ant.sml
alicerun ant 1 5 1000 200 0          (result *4)

ghc --make -threaded -O2 ant.hs
time ./ant 1 1000 +RTS -K500m -H1000m -N1
time ./ant 1 1000 +RTS -K500m -H1000m -N2
time ./ant 1 1000 +RTS -K500m -H1000m -N3
time ./ant 1 1000 +RTS -K500m -H1000m -N4

scalac -optimize Ant.scala
scala Ant serial
scala Ant

erl -smp enable +S 1 -pa .
erl -smp enable +S 2 -pa .
erl -smp enable +S 3 -pa .
erl -smp enable +S 4 -pa .

ocamlopt -o ant unix.cmxa
time ./ant 1 5 1000 200


Erlang and Alice SML omitted from graph. Note change from previous tests: 1000 interations, instead of 100. Still 200 cities.

Cores   Erlang   Haskell   Scala   OCaml   MLton_SML  Alice_SML
1       372      86        41.6            6.0        676
2       192      63
3       141      58
4       98       54        14.6    1.6
All times in seconds.


MLton Standard ML
Alice Standard ML
OCaml: forking implemention posted by Jon Harrop to comp.lang.functional


Previous discussions in comments in post1, post2, and (possibly :-) new post3.


Added Ant Colony Optimization for TSP in Psyco Python.